//692. 前K个高频单词
// 思路：将字符元素放入map，然后转入vector<pair<string, int>>，进而排序，再返回前k个的string即可

#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// bool cmp(const pair<string, int>& s1, const pair<string, int>& s2)
// {
//     if(s1.second == s2.second) return s1.first < s2.first;// 题目要求以字典序排
//     else return s1.second > s2.second;// 由大到小的顺序排
// }
// class Solution
// {
// public:
//     vector<string> topKFrequent(vector<string>& words, int k)
//     {
//         map<string, int> m;
//         for(auto& word : words)
//         {
//             m[word]++;
//         }

//         vector<pair<string, int>> tmp(m.begin(), m.end());
//         sort(tmp.begin(), tmp.end(), cmp);
        
//         vector<string> ret;
//         for(int i = 0; i < k; i++)
//         {
//             ret.push_back(tmp[i].first);
//         }
//         return ret;
//    }
// };


// 仿函数版本
class Solution
{
public:
    struct kvCom
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
        {
            // 出现频率高的排前面，如果频率相同，按照字典序排
            return kv1.second > kv2.second 
                || (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        map<string, int> countMap;
        for(auto& word : words)
        {
            countMap[word]++;
        }

        vector<pair<string, int>> sortV(countMap.begin(), countMap.end());
        sort(sortV.begin(), sortV.end(), kvCom());
        
        vector<string> ret;
        for(int i = 0; i < k; i++)
        {
            ret.push_back(sortV[i].first);
        }
        return ret;
   }
};